import java.lang.*; import java.awt.*; import java.awt.event.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Scanner;


public class Heuristica {
	private Nodo [][]nodos;
	private ArrayList<Nodo> frontera;
	private ArrayList<Nodo> interior;
	private int x0,xf,y0,yf;
	private posicion objetivo;
    private posicion pos ;
    private int filas;
    private int columnas;
    private ArrayList lista_hijos = new ArrayList();
    private int [][]matriz;  //={{0,1,2,3,4},{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19}};
    private posicion [][]padre;
    private int TipoDistanciaHeuristica;
    
public static void main(String[] args) {
	
	  String[][] array={{"Zanahoria","Apio","Espinaca","Lechuga","Esparrago"},
			            {"Naranja","Platano","Sandia","Kiwi","Fresas"},
                        {"Leche","Yoghurt","Queso","Crema","Mantequilla"},
                        {"Res","Pollo","Cerdo","Pescado","Mariscos"}};
	

	System.out.println("Verduras: | 0,0: Zanahoria  0,1: Apio     0,2: Espinaca  0,3: Lechuga  0,4: Esparrago  |\n" +
			           "Frutas  : | 1,0: Naranja    1,1: Platano  1,2: Sandia    1,3: Kiwi     1,4: Fresas     |\n" +
					   "Lacteos : | 2,0: Leche      2,1: Yoghurt  2,2: Queso     2,3: Crema    2,4: Mantequilla|\n" +
			           "Carnes  : | 3,0: Res        3,1: Pollo    3,2: Cerdo     3,3:Pescado   3,4: Mariscos   |\n");
	
	System.out.println("Selecciona cual es tu ubicacion: ");
	System.out.println("X: ");
	Scanner ux=new Scanner(System.in);
	String Xubicacion=ux.next();
	System.out.println("Y: ");
	Scanner uy=new Scanner(System.in);
	String Yubicacion=uy.next();
	int yu=Integer.parseInt(Yubicacion);
	int xu=Integer.parseInt(Xubicacion);
	
	System.out.println("Selecciona a donde quieres ir: ");
	System.out.println("X: ");
	Scanner dx=new Scanner(System.in);
	String Xdestino=dx.next();
	System.out.println("Y: ");
	Scanner dy=new Scanner(System.in);
	String Ydestino=dy.next();
	int yd=Integer.parseInt(Ydestino);
	int xd=Integer.parseInt(Xdestino);
	
	System.out.println("Tu ubicacion es: "+ array[xu][yu]);
	System.out.println("Quieres ir a: "+array[xd][yd]);
	
	
	Heuristica iniciar=new Heuristica(3, 4, xu, yu, xd, yd, 1);

	
}


     public Heuristica(int Nfilas,int Ncolumnas,int inicialX,int inicialY,int finalX,int finalY, int TipoDistanciaHeuristica){
    	  
    	  
       
        this.TipoDistanciaHeuristica = TipoDistanciaHeuristica;
        
        this.matriz = new int[Nfilas][Ncolumnas];
        this.padre = new posicion[Nfilas][Ncolumnas];

        for (int i=0;i<Nfilas;i++)
            for (int j=0;j<Nfilas;j++){
                this.matriz[i][j] = matriz[i][j];

            }


    }

    
    public boolean isEmpty(){
    	return lista_hijos.isEmpty();
    	}
     
     
    public boolean Heuristica(){//int [][]matriz, posicion [][]padre){
                
        // meter todos los hijos por orden en la lista
        posicion aux = new posicion(); 
        
        System.out.println("Soy el Padre: "+ pos.getPos_x()+ " "+pos.getPos_y());
        aux = this.getNorte();        
        if (aux != null){            
            if((matriz[aux.getPos_x()][aux.getPos_y()] != 1)&&(matriz[aux.getPos_x()][aux.getPos_y()] != 5)){  
                System.out.println("Soy el Norte: "+ aux.getPos_x()+ " "+aux.getPos_y());
                padre[aux.getPos_x()][aux.getPos_y()] = pos;
                //asigno valor heuristico al hijo
                if (TipoDistanciaHeuristica == 1)
                    aux.calculo_manhattan(objetivo);
                else if (TipoDistanciaHeuristica == 2)
                    aux.calculo_euclidiano(objetivo);
                else if (TipoDistanciaHeuristica == 3)
                    aux.calculo_cuadrada(objetivo);
                else if (TipoDistanciaHeuristica == 4)
                    aux.calculo_camberra(objetivo);
            
                aux.setCamino(pos.get_Camino() + 1);
                aux.setTotal();
                if (matriz[aux.getPos_x()][aux.getPos_y()] == 3)
                    return true;

                lista_hijos.add(insertarEnPos(aux.get_heu()),aux);

                matriz[aux.getPos_x()][aux.getPos_y()] = 5;              
            }
        }

        aux = this.getEste();        
        if (aux != null){           
           if((matriz[aux.getPos_x()][aux.getPos_y()] != 1)&&(matriz[aux.getPos_x()][aux.getPos_y()] != 5)){ 
                System.out.println("Soy el Este: "+ aux.getPos_x()+ " "+aux.getPos_y());
                padre[aux.getPos_x()][aux.getPos_y()] = pos;
                
                if (TipoDistanciaHeuristica == 1)
                    aux.calculo_manhattan(objetivo);
                else if (TipoDistanciaHeuristica == 2)
                    aux.calculo_euclidiano(objetivo);
                else if (TipoDistanciaHeuristica == 3)
                    aux.calculo_cuadrada(objetivo);
                else if (TipoDistanciaHeuristica == 4)
                    aux.calculo_camberra(objetivo);
                
                aux.setCamino(pos.get_Camino() + 1);
                aux.setTotal();
                
                if (matriz[aux.getPos_x()][aux.getPos_y()] == 3)
                    return true;
                
                //si aux es mayor lo meto delante siempre que la lista no tenga un solo valor
                lista_hijos.add(insertarEnPos(aux.get_heu()),aux);

                matriz[aux.getPos_x()][aux.getPos_y()] = 5;                
            }
        }
        
        aux = this.getSur();        
        if (aux != null){            
            if((matriz[aux.getPos_x()][aux.getPos_y()] != 1)&&(matriz[aux.getPos_x()][aux.getPos_y()] != 5)){  
                System.out.println("Soy el Sur: "+ aux.getPos_x()+ " "+aux.getPos_y());
                padre[aux.getPos_x()][aux.getPos_y()] = pos;
                
                if (TipoDistanciaHeuristica == 1)
                    aux.calculo_manhattan(objetivo);
                else if (TipoDistanciaHeuristica == 2)
                    aux.calculo_euclidiano(objetivo);
                else if (TipoDistanciaHeuristica == 3)
                    aux.calculo_cuadrada(objetivo);
                else if (TipoDistanciaHeuristica == 4)
                    aux.calculo_camberra(objetivo);
                
                aux.setCamino(pos.get_Camino() + 1);
                aux.setTotal();
                if (matriz[aux.getPos_x()][aux.getPos_y()] == 3)
                    return true;
                
                //si aux es mayor lo meto delante siempre que la lista no tenga un solo valor
                lista_hijos.add(insertarEnPos(aux.get_heu()),aux);

                matriz[aux.getPos_x()][aux.getPos_y()] = 5;               
            }
        }

        aux = this.getOeste();        
        if (aux != null){           
           if((matriz[aux.getPos_x()][aux.getPos_y()] != 1)&&(matriz[aux.getPos_x()][aux.getPos_y()] != 5)){ 
                System.out.println("Soy el Oeste: "+ aux.getPos_x()+ " "+aux.getPos_y());  
                padre[aux.getPos_x()][aux.getPos_y()] = pos;
                
                if (TipoDistanciaHeuristica == 1)
                    aux.calculo_manhattan(objetivo);
                else if (TipoDistanciaHeuristica == 2)
                    aux.calculo_euclidiano(objetivo);
                else if (TipoDistanciaHeuristica == 3)
                    aux.calculo_cuadrada(objetivo);
                else if (TipoDistanciaHeuristica == 4)
                    aux.calculo_camberra(objetivo);
                
                aux.setCamino(pos.get_Camino() + 1);
                aux.setTotal();
                if (matriz[aux.getPos_x()][aux.getPos_y()] == 3)
                    return true;
                
                //si aux es mayor lo meto delante siempre que la lista no tenga un solo valor
               lista_hijos.add(insertarEnPos(aux.get_heu()),aux);

                matriz[aux.getPos_x()][aux.getPos_y()] = 5;               
            }
        }
        
        lista_hijos.remove(0); 
        
        //llama a una calse que puse al principio de este fichero y que ordena la lista en funcion del valor heuristico habira k mirar esta parte bien 
        //System.out.println((new MyComp().orderCallNumbers(lista_hijos)));  // imprimir la lista ordenada y creo que la ordenada tb, el problema es que imprime las direcciones de memoria
        for(int i=0; i<lista_hijos.size();i++)
                   System.out.println("->[" +((posicion)lista_hijos.get(i)).getPos_x() +"-"+((posicion)lista_hijos.get(i)).getPos_y()+"] = "+((posicion)lista_hijos.get(i)).get_heu());
        
        if (!lista_hijos.isEmpty()){
            
            matriz[pos.getPos_x()][pos.getPos_y()] = 5;
            pos = (posicion)lista_hijos.get(0);
            matriz[pos.getPos_x()][pos.getPos_y()] = 2;
        }
        return false;
        
    }

    public posicion getNorte(){
        posicion aux = new posicion();
        if ((pos.getPos_x()-1)>=0){
            aux.setPos((pos.getPos_x()-1),pos.getPos_y());
            return aux;
        }
        return null;        
    }
    public posicion getEste(){
        posicion aux = new posicion();
        if ((pos.getPos_y()+1)<columnas){
            aux.setPos(pos.getPos_x(),(pos.getPos_y()+1));
            return aux;
        }
        return null;        
    }
    public posicion getSur(){
        posicion aux = new posicion();
        if ((pos.getPos_x()+1)<filas){
            aux.setPos((pos.getPos_x()+1),pos.getPos_y());
            return aux;
        }
        return null;        
    }
    public posicion getOeste(){
        posicion aux = new posicion();
        if ((pos.getPos_y()-1)>=0){
            aux.setPos(pos.getPos_x(),(pos.getPos_y()-1));
            return aux;
        }
        return null;        
    }
    
    public ArrayList getCamino(posicion inicial){//,posicion [][]padre){
        ArrayList auxlista= new ArrayList();
        posicion auxpos = new posicion(pos);
        auxlista.add(0,auxpos);
        auxpos = padre[pos.getPos_x()][pos.getPos_y()];
        while (!auxpos.isEquals(inicial)){
            auxlista.add(0,auxpos);
            auxpos = padre[auxpos.getPos_x()][auxpos.getPos_y()];    
        }          
        auxlista.add(0,auxpos);
        return auxlista;        
    }
    
        public int insertarEnPos(int valor){
             for(int i=1; i<lista_hijos.size();i++)
                 if (((posicion)lista_hijos.get(i)).get_heu() > valor)
                     return i;
            return lista_hijos.size();        
        }
         public int insertarEnPos(long valor){
             for(int i=1; i<lista_hijos.size();i++)
                 if (((posicion)lista_hijos.get(i)).get_heu() > valor)
                     return i;
            return lista_hijos.size();        
        }
}
